package sorting;

import util.ArrayUtil;
import util.MathUtil;
import util.Tracer;

public class Selection {
	public static float select(float[] numbers, int order)
	{
		return select(numbers, 0, numbers.length - 1, order);
	}
	
	public static float select1(float[] numbers, int order)
	{
		int part = -1;
		int p = 0;
		int r = numbers.length - 1;
		while(part != order)
		{
			if(part < order)
			{
				p = part + 1;
			}
			else if(part > order)
			{
				r = part - 1;
			}

			ArrayUtil.each(numbers, r, MathUtil.random(p, r));
			part = partition(numbers, p, r);
		}
		
		return numbers[part];
	}
	
	public static float select(float[] numbers, int p, int r, int order)
	{
		ArrayUtil.each(numbers, r, MathUtil.random(p, r));
		int part = partition(numbers, p, r);
		if(part > order)
		{
			return select(numbers, p, part - 1, order);
		}
		else if(part < order)
		{
			return select(numbers, part + 1, r, order);
		}
		else
		{
			return numbers[part];
		}
	}
	
	public static int partition(float[] numbers, int p, int r)
	{
		float pivot = numbers[r];
		int q = p;
		for(int i = p; i < r; i ++)
		{
			if(numbers[i] < pivot)
			{
				ArrayUtil.each(numbers, i, q ++);
			}
		}
		
		ArrayUtil.each(numbers, q, r);
		return q;
	}
	
	public static void main(String[] args) {
		Tracer.trace(select1(new float[]{5, 9, 1, 2, 8, 4, 6, 0, 7}, 7));
	}
}
